[level 4] 올바른 괄호의 갯수 - 12929

문제 링크

문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 이 주어질 때, 개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

제한사항

• 괄호 쌍의 개수 : , 은 정수

---

입출력 예

n	result
2	2
3	5

입출력 예 설명

입출력 예 #1 2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다.

입출력 예 #2 3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만들 수 있습니다.

---

구현 코드

import java.util.*;

class Solution {

    public class Box{
        public String str; // 문자열
        public int l; // '(' 갯수
        public int r; // ')' 갯수
        Box(String str, int l, int r){
            this.str = str;
            this.l = l;
            this.r = r;
        }
    }

    int answer;

    public int solution(int n) {

        Queue<Box> q = new LinkedList<>();
        answer =0;
        Box first = new Box("(",1,0); // 괄호쌍은 항상 '('로 시작
        q.add(first);

        while(!q.isEmpty()){

            Box b = q.poll();
            if(b.l<b.r){ continue; } // 모든인덱스 기준 ')'가 '('보다 많을 수 없음
            if(b.str.length()==2*n){ // 완성된 괄호쌍이 가능한지 검사
                check(b.str);
            }else{
                //각각의 문자는 n개보다 많을 수 없음
                if(b.l<n){ q.add(new Box(b.str+'(', b.l+1, b.r)); }
                if(b.r<n){ q.add(new Box(b.str+')', b.l, b.r+1)); }
            }
        }
        return answer;
    }
    //stack을 사용해서 하는게 국롤이지만 그냥 사용하지 않았다.
    public void check(String str){
        int count =0;
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)=='('){ count++; }
            else{
                if(count<=0){ return; }
                else{ count--; }
            }
        }
        if(count==0){ answer++; }
    }
}

성능 요약

메모리: 1.54 GB, 시간: 6035.57 ms

채점결과

정확성: 100.0

합계: 100.0 / 100.0